package daily.year2024.m8;

public class d17 {
    class Solution {
        //解法一：反转+前缀和+二分
        public int longestOnes(int[] nums, int k) {
            int n = nums.length;
            int[] prefix = new int[n+1];
            for(int i=0;i < n;i++) {
                prefix[i+1] = prefix[i] + (nums[i]^1);
            }
            int res = 0;
            for(int i=0;i < n;i++) {
                int target = prefix[i+1] - k;
                int start = halfSearch(0,i-1,target,prefix);
                res = Math.max(res,i-start+1);
            }
            return res;
        }
        //二分查找，找到第最小的达到 prefix[r] - prefix[l] <= k 的位置
        //变换等式得到：prefix[l] >= prefix[r] - k ，即找到第一个大于这个值的l下标
        private int halfSearch(int l, int r, int target, int[] prefix) {
            while(l < r) {
                int c = l + ((r-l) >> 1);
                if(prefix[c] < target) {
                    l = c + 1;
                } else {
                    r = c;
                }
            }
            return l;
        }
    }

    class Solution2 {
        //解法二：滑动窗口
        public int longestOnes(int[] nums, int k) {
            int n = nums.length;
            int l = 0, r = 0;
            int lsum = 0, rsum = 0;
            int res = 0;
            for(;r < n;r++) {
                rsum += nums[r] ^ 1;
                //要将左边界收缩
                while(rsum - lsum > k) {
                    lsum += nums[l] ^ 1;
                    l++;
                }
                res = Math.max(res, r-l+1);
            }
            return res;
        }
    }
}
